<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      let tree = {
        val: 1,
        left: {
          val: 2,
          left: {
            val: 4
          },
          right: {
            val: 5
          }
        },
        right: {
          val: 3,
          left: {
            val: 6,
            left: {
              val: 8
            },
            right: {
              val: 9
            }
          },
          right: {
            val: 7
          }
        }
      }
      function travelTree(root) {
        let res = []
        function backTracking(path, root) {
          if (!root.left && !root.right) {
            return res.push([...path])
          }
          if (root.left) {
            path.push(root.left.val)
            backTracking(path, root.left)
            path.pop()
          }
          if (root.right) {
            path.push(root.right.val)
            backTracking(path, root.right)
            path.pop()
          }
        }
        backTracking([root.val], root)
        return res
      }
      console.log(travelTree(tree))
    </script>
  </body>
</html>
